package com.lm.leetcode.briefsummary;

/**
 * @Auther: Min.Liu
 * @Description: 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
 * 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
 * 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
 * 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
 * <p>
 * 给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
 * 你必须设计一个时间复杂度为O(log n) 的算法解决此问题。
 * @Date: Created in 11:20 2025/5/20
 */
public class findMinDemo {
    public static void main(String[] args) {
        findMinDemo demo = new findMinDemo();
        int[] arr = {4,5,1,2,3};
        int[] arr1 = {3,4,5,1,2};
        int[] arr2 = {2,1};
        int[] arr3 = {3,1,2};
        int[] arr4 = {2,3,1};
        //int[] arr2 = {1, 2, 3, 4, 5};
        System.out.println(demo.findMin(arr));
        System.out.println(demo.findMin(arr1));
        System.out.println(demo.findMin(arr2));
        System.out.println(demo.findMin(arr3));
        System.out.println(demo.findMin(arr4));
    }

    /**
     * 思路：
     *     先判断首末：首<末，首就是最小值
     *     再判断首末谁更靠近中值：
     *     中值>首，则中值更靠近末尾，说明从后往前遍历路径更短；反之，则中值更接近开头，从前往后遍历路径更短
     */
    public int findMin(int[] nums) {
        int len = nums.length-1;
        if (len==0) {
            return nums[0];
        }else if(len==1){
            return nums[0]>nums[1]?nums[1]:nums[0];
        }
        int mid = len/2;
        System.out.print(mid+"==>");
        if(nums[0]<nums[len]){
            return nums[0];
        }
        if(nums[0]<nums[mid]){ //从后往前  不超过mid
            for (int i = len; i > mid; i--) {
                if (nums[i-1] > nums[i]) {
                    return nums[i];
                }
            }
        }else{ //从前往后  不超过mid
            for (int i = 0; i < mid; i++) {
                if (nums[i] > nums[i + 1]) {
                    return nums[i + 1];
                }
            }
        }
        return nums[0];
    }
}
